package com.itheima.datastructure.heap;
/*
求数组第k大的元素
 */
public class E02Leetcode215 {
    /*
    解题思路：
    1.向小顶堆放入前k个元素
    2.剩余元素：
    如果<=堆顶,就略过
    >堆顶，替换为堆顶元素
    3.这样小顶堆保持前k大的元素，第K大的元素为堆顶元素
     */
    public int findKthLargest(int [] numbers,int k){
        MinHeap heap=new MinHeap(k);
        for(int i=0;i<k;i++){
            heap.offer(numbers[i]);
        }
        for(int i=k;i<numbers.length;i++){
            if(numbers[i]>heap.peek()){
                heap.replace(numbers[i]);
            }
        }
    return heap.peek();
    }

    public static void main(String[] args) {
        System.out.println(new E02Leetcode215().findKthLargest(new int[]{3,2,1,5,6,4},2));
    }
}
